#include <stdio.h>
#include <stdlib.h>
void show(int arr[], int len) {
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));//分配内存，构建一个相同大小的数列
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            show(b, len);
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            printf("start1=%d,end1=%d,start2=%d,end2=%d\n",start1,end1,start2,end2);
            while (start1 < end1 && start2 < end2)            {                
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
                //printf("b[%d]=%d\n", k,b[k-1]);
                //show(b, len);
            }
            while (start1 < end1){
                b[k++] = a[start1++];
                //printf("b[%d]=%d\n", k,b[k-1]);
                //show(b, len);
            }
            while (start2 < end2){
                b[k++] = a[start2++];
                //printf("b[%d]=%d\n", k,b[k-1]);
                //show(b, len);
            }
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}
int main()
{
    int arr[] = {78,8982,11, 7,  3, 4,2, 5, 6, 10, 8, 9, 1,23,40,99,100,32,1 };
    int len = sizeof(arr) / sizeof(arr[0]);
    show(arr, len);
    merge_sort(arr, len);
    show(arr, len);
    return 0;
}